package org.example;

import org.junit.jupiter.api.Test;

import javax.swing.plaf.metal.OceanTheme;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;
import java.util.stream.Stream;

public class Stair {

    @Test
    void backtrack4ClimbStair() {
        int[] choices = {1, 2};
        int target = 3;
        List<List<Integer>> res = new ArrayList<>();
        backtrack4ClimbStair(new ArrayList<>(), choices, target, res);
        for (List<Integer> re : res) {
            System.out.println(re.stream().map(String::valueOf).collect(Collectors.joining()));
        }
        System.out.println(res.size());
    }

    /**
     * 楼梯回溯
     * @param state
     * @param choices
     * @param target
     * @param res
     */
    void backtrack4ClimbStair(List<Integer> state,
                              int[] choices,
                              int target,
                              List<List<Integer>> res) {
        if (state.stream().mapToInt(Integer::intValue).sum() == target) {
            res.add(new ArrayList<>(state));
            return;
        }

        for (int i = 0; i < choices.length; i++) {
            if (state.stream().mapToInt(Integer::intValue).sum() > target) {
                continue;
            }
            int choice = choices[i];
            state.add(choice);
            backtrack4ClimbStair(state, choices, target, res);
            state.remove(state.size() - 1);
        }
    }

    @Test
    void dfs() {
        System.out.println(dfs(3));
    }

    /**
     * 深度搜索
     * @param i
     * @return
     */
    int dfs(int i) {
        if (i == 1 || i == 2) {
            return i;
        }

        return dfs(i - 1) + dfs(i - 2);
    }

    @Test
    void dfsWithMem() {
        int n = 3;
        int[] mem = new int[n + 1];
        Arrays.fill(mem, -1);
        System.out.println(dfsWithMem(n, mem));
    }

    /**
     * 带记事本的回溯
     * @param i
     * @param mem
     * @return
     */
    int dfsWithMem(int i,
                   int[] mem) {

        if (i == 1 || i == 2) {
            return i;
        }

        if (mem[i] != -1) {
            return mem[i];
        }

        return mem[i] = dfsWithMem(i - 1, mem) + dfsWithMem(i - 2, mem);
    }

    @Test
    void dp() {
        int dp = dp(3);
        System.out.println(dp);
    }

    /**
     * 动态规划
     * @param n
     * @return
     */
    int dp(int n) {
        if (n == 1 || n == 2) {
            return n;
        }

        int[] dp = new int[n + 1];
        dp[1] = 1;
        dp[2] = 2;

        for (int i = 3; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }

    /**
     * 带权重动态规划
     * @param cost
     * @return
     */
    int dpWithCost(int[] cost) {
        int n = cost.length - 1;
        if (n == 1 || n == 2) {
            return cost[n];
        }

        int[] dp = new int[n + 1];
        dp[1] = cost[1];
        dp[2] = cost[2];
        for (int i = 3; i <= n; i++) {
            dp[i] = Math.min(dp[i - 1], dp[i - 2]) + cost[i];
        }

        return dp[n];
    }

    @Test
    void dpWithLimit() {
        int i = dpWithLimit(11);
        System.out.println(i);
    }

    /**
     * 带限制动态规划
     * @param n
     * @return
     */
    int dpWithLimit(int n) {
        if (n == 1 || n == 2) {
            return 1;
        }

        int[] dp1 = new int[n + 1];
        int[] dp2 = new int[n + 1];
        dp1[1] = 1;
        dp1[2] = 0;
        dp2[1] = 0;
        dp2[2] = 2;
        for (int i = 3; i <= n; i++) {
            dp1[i] = dp2[i - 1];
            dp2[i] = dp2[i - 2] + dp1[i - 2];
        }
        return dp1[n] + dp2[2];
    }

    @Test
    void climbingStairsConstraintDP() {
        int i = climbingStairsConstraintDP(11);
        System.out.println(i);
    }

    /* 带约束爬楼梯：动态规划 */
    int climbingStairsConstraintDP(int n) {
        if (n == 1 || n == 2) {
            return 1;
        }
        // 初始化 dp 表，用于存储子问题的解
        int[][] dp = new int[n + 1][3];
        // 初始状态：预设最小子问题的解
        dp[1][1] = 1;
        dp[1][2] = 0;
        dp[2][1] = 0;
        dp[2][2] = 1;
        // 状态转移：从较小子问题逐步求解较大子问题
        for (int i = 3; i <= n; i++) {
            dp[i][1] = dp[i - 1][2];
            dp[i][2] = dp[i - 2][1] + dp[i - 2][2];
        }
        return dp[n][1] + dp[n][2];
    }

    /**
     * 最短路径
     */
    @Test
    void shortestPath() {
        int[][] grid = {{1, 3, 1, 5}, {2, 2, 4, 2}, {5, 3, 2, 1}, {4, 3, 5, 2}};
        int m = grid.length;
        int n = grid[0].length;

        int[][] dp = new int[m][n];
        dp[0][0] = grid[0][0];
        for (int col = 1; col < n; col++) {
            dp[0][col] = dp[0][col - 1] + grid[0][col];
        }

        for (int row = 1; row < m; row++) {
            dp[row][0] = dp[row - 1][0] + grid[row][0];
        }

        for (int row = 1; row < m; row++) {
            for (int col = 1; col < n; col++) {
                dp[row][col] = Math.min(dp[row - 1][col], dp[row][col - 1]) + grid[row][col];
            }
        }

        System.out.println(dp[m - 1][n - 1]);
    }

    @Test
    void shortestPathV2() {
        int[][] grid = {{1, 3, 1, 5}, {2, 2, 4, 2}, {5, 3, 2, 1}, {4, 3, 5, 2}};
        int m = grid.length;
        int n = grid[0].length;

        int[] dp = new int[n];
        dp[0] = grid[0][0];
        for (int col = 1; col < n; col++) {
            dp[col] = dp[col - 1] + grid[0][col];
        }

        for (int row = 1; row < m; row++) {
            dp[0] = dp[0] + grid[row][0];
            for (int col = 1; col < n; col++) {
                dp[col] = Math.min(dp[col], dp[col - 1]) + grid[row][col];
            }
        }

        System.out.println(dp[n - 1]);
    }
}
